% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode

% This is a simple template for a LaTeX document using the "article" class.
% See "book", "report", "letter" for other types of document.

\documentclass[11pt]{article} % use larger type; default would be 10pt

\usepackage[utf8]{inputenc} % set input encoding (not needed with XeLaTeX)

%%% Examples of Article customizations
% These packages are optional, depending whether you want the features they provide.
% See the LaTeX Companion or other references for full information.

%%% PAGE DIMENSIONS
\usepackage{geometry} % to change the page dimensions
\geometry{a4paper} % or letterpaper (US) or a5paper or....
% \geometry{margin=2in} % for example, change the margins to 2 inches all round
% \geometry{landscape} % set up the page for landscape
%   read geometry.pdf for detailed page layout information

\usepackage{graphicx} % support the \includegraphics command and options

% \usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent

%%% PACKAGES
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
% These packages are all incorporated in the memoir class to one degree or another...

\usepackage{url}
\usepackage[lined,algonl,boxed]{algorithm2e}
\usepackage{cite}


%%% HEADERS & FOOTERS
\usepackage{fancyhdr} % This should be set AFTER setting up the page geometry
\pagestyle{fancy} % options: empty , plain , fancy
\renewcommand{\headrulewidth}{0pt} % customise the layout...
\lhead{}\chead{}\rhead{}
\lfoot{}\cfoot{\thepage}\rfoot{}

%%% SECTION TITLE APPEARANCE
\usepackage{sectsty}
\allsectionsfont{\sffamily\mdseries\upshape} % (See the fntguide.pdf for font help)
% (This matches ConTeXt defaults)

%%% ToC (table of contents) APPEARANCE
\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!

%%% END Article customizations

%%% The "real" document content comes below...

\title{GPU and Large Graph Data Representations}
\author{Z. Mahomed  \hspace{20 mm} Dr. J. Burns}
\date{         2013} % Activate to display a given date or no date (if empty),
         % otherwise the current date is printed 


\begin{document}
\maketitle

\section{Introduction}

Social network analysis (SNA) is a very computationally intensive process. This becomes obvious when discussing the data representation of the networked graph. The most basic representation is the Adjacency Matrix,a square matrix. An adjacency matrix is a $n x n $ matrix where the non-diagonal entry $a_ij$ is the weight value from vertex $i$ to vertex $j$, and the diagonal entry $aii$ can be used to count contact between the vetex and it self. This graph is convenient to work with but are inefficient for large sparse graphs, which is the characteristic of Social Networks. Therefore the Sparse Adjacency Matrix needs to be manipulated and represented in a more efficient manner.


\subsection{Types of Graph Representations}

In order to process massive graphs, it is particularly important that the data structures are space efficient. Ease of parallelisation and the synchronisation overhead also influences our representation choice. Ideally the structure needs to be simple, scalable and low over head. 

For static graphs adjacency lists can be implemented using cache friendly adjacency arrays to give performance improvements over adjacency matrix representations of a sparse graph.For dynamic networks the process needs to manage insertions of vertices and edges which may be batched or streamed.

The coordinate storage scheme (COO) can be used to compress a sparse matrix into a direct transformation from the dense format. $N_z$ is the total number of non-zero entries in the matrix. COO typically uses three one dimensional arrays of size $N_z$. The first being floating point numbers, containing every non-zero entity. The other two arrays of integers contain the corresponding row and column indices for each non zero entry.

Compressed Row Storage (CRS) is the most extended format to store matrices. Let $N$ and $N_z$ be the number of rows of the matrix and the total number of non zero entries of the matrix. The data structure consists of the three following arrays. $A[]$ an array of floats of dimension $N_z$, which stores the entries. Then $j[]$ an array of integers of dimension $N_z$ which stores the column index and finnaly the $start[]$ which is an array of integers of dimension N which stores the pointers to the begining of every row in $A[]$ and $j[]$. There is a modified version of this called CRS with Negative (CRSN) which only requires two arrays of dimension $N_z$ which are equivalent to arrays $A[]$ and $j[]$ of the original CRS. The difference being the beginning of every row is marked with a negative column index in $j[]$. Their is a slight improvement on CRSN compared to the previous CRS even when scaled up.


A final more  option is a vector graph, for the graph data representation. This uses a segmented vectors to store the graph topology. It uses a single segmented vector to store edge information. Each segment corresponds to a vertex and each element within a segment corresponds to one of the edges of that vertex. A graph can be converted from most of the other representations into a vertex graph representation by creating two elements per edge, one for each end, and sorting the edges according to their vertex number. Parallel sorting algorithms can be used to place all the edges that belong to the same vertex in a contiguous segment. This cross-pointer array in this representations enables a $O(1)$ complexity of a dynamic graph manipulations such as adding or deleting an edge or vertex. Which is not possible with other representations. This however is more useful for a directed and weighted network, which may be unnecessary for the given dataset.
 \\


\bibliographystyle{plain}
\bibliography{Reading}{}




\end{document}
